#define _CRT_SECURE_NO_WARNINGS 1
int numDecodings(char* s) {
    int n = strlen(s);
    int* dp = (int*)malloc(sizeof(int) * (n + 1));
    memset(dp, 0, sizeof(int) * n + 4);
    dp[0] = 1;
    if (s[0] != '0')
        dp[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        if (s[i - 1] != '0')
            dp[i] += dp[i - 1];
        int t = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
        if (t <= 26 && t >= 10)
            dp[i] += dp[i - 2];
    }
    return dp[n];
}